Polar GP
怎么这么困难
被大佬带飞
Two Spanning Trees
并非简单题
你先搞出来一棵 A 的生成树，如果它不是 B 的生成树，那么直接返回它即可。
然后我就不会做了……
首先你发现取 n−1 条边而不构成树，那么必然会构成环。
那么你发现我们只要取到一个边集 C，使得 C 在 B 中构成环，且在 A 中不构成环（即构成森林）即可。
得到他之后，只要在 A 的各连通块中任意连边即可得到一个合法解，所以这是充要的。
考虑上面找到的生成树，记为 T。
为了方便，我们决定考虑所有的环图，即度数等于 0 或 2 的图，显然是等价的。
根据环基方面的理论，我们知道 B 的所有环子图，由所有 T 的非树边生成。
考虑所有 T 的非树边 e，即 e∈/T，定义 {e}∪s1(e) 表示 e 在 A 的 T 上生成的环，s2 类似。
如果我们找到一个 s1(e)⊈s2(e)，那么 {e}∪s2(e) 直接就是一组解。
所以现在所有 s1(e)⊆s2(e)。
考虑答案的环基是 E，是所有非树边的一个子集。
那么我们要求 E∪⨁e∈Es2(e) 在 A 中形如一片森林。
记 Cyc2(E)=⨁e∈Es2(e)，Cyc1 类似。
则我们要求 ∀E′⊆E,Cyc1(E′)⊈Cyc2(E)。
引入神秘记号：记 e∼e′，如果 s1(e)∩s1(e′)=∅。记 e≈e′，如果存在 e∼e1∼e2∼⋯∼ek∼e′。
显然可达性 ≈ 为一等价关系，可以把 E 划分为 E1⊔E2⊔⋯⊔Ek。
注意到
Cyc2(E)=Cyc1(E1)⊕e∈E1⨁(s2(e)⊕s1(e))⊕Cyc2(E\E1)=Cyc1(E1)⊕e∈E1⨁(s2(e)\s1(e))⊕Cyc2(E\E1)
由于 Cyc1(E1)⊈Cyc2(E)，所以要么存在 e∈E1,s2(e)\s1(e)∩Cyc1(E1)=∅，要么存在 e∈E\E1,s2(e)∩Cyc1(E1)=∅。
无论如何，都必然存在 e∈E,(s2(e)\s1(e))∩Cyc1(E1)=∅。
记 e1→e2，如果 (s2(e1)\s1(e1))∩s1(e2)=∅
于是根据 ∼ 和 → 可以建出一个混合图 G。
根据上面的结论，任意一个 ∼ 的连通块都必然存在一条入边。
可以证明 G 中任意一个至少包含一个 → 的简单环都是合法的。
所以可以建图跑 Tarjan，只要存在强连通分量内部包含至少一条 → 即合法。
Christmas Tree
注意到每个点的贡献是它能够到达的点的个数。
设 fu,i 表示 u 能够到达子树外的点的个数为 i 时，u 的子树内的最小代价和。
但是我场上发现，当我想要每次加入一个儿子时，我还要知道 u 在子树内能够到达多少个点，这样肯定会超时。
其实你发现，如果 u 的父边向其父亲，那么我们只想知道它能够到达子数外多少个点；否则我们只想知道它能够到达子树内多少个点。
所以我们再设 gu,i 表示 u 能够到达子树内的点的个数为 i 时，u 的子树内的最小代价和。
转移时不妨预定 u 总共能到达点的个数 k，于是转移形如树上背包。
注意到我们总是从小的 k 转移到大的 k，因此外层枚举了一个 k 之后不难做到 O(n2) 树上背包，所以总复杂度为 O(n3)。
Roman Numerals
赛时猜了一个错误的结论：以为每个点的相对系数不变，所以乘上 LCA 的系数即可。
发现假掉之后，吸取教训想了想 CDQ 分治，但是没想出来。
实际上你发现，找到 LCA 即最大值之后，变成左边剩一个后缀，右边剩一个前缀。
你发现：如果我们算出整个数组的一个后缀的答案，再减去 LCA 及以后的部分的话，刚好就是整个后缀的贡献；前缀同理。
而我们刚好有 O(N) 或者 O(NlogN) 增量构造笛卡尔树的方法。
一个类似扫描线单调栈的东西维护右链
Disjoint Set Splitting
场上首先想出一个错误做法：先随便搞出一棵生成树，维护每条树边有没有删去，以及维护已被删去的树边上的覆盖的非树边的数目。
然后我奋斗 1h+ 写了一个树剖线段树，贡献一发罚时之后，发现做法假掉了……
想想也是，要是动态树那么简单，大家还写什么 LCT 和 ETT 呢？
然后我思考半晌，发现这个强制在线是假的！
具体来说，由于答案一定是一段前缀 1 加上一段后缀 0，而且我们不用管后缀 0 阶段的输入，所以我们其实是可以算出来解密后的输入是什么的。
然后我光速写了一个二分+DFS 的交了上去，然后发现被卡了……
不是你 O(nlogn),n≤106 跑进 2.5s 不是稀疏平常的事情吗卡我干什么啊
冷静一下，发现二分是没有必要的。
我们像那个模板题那样倒序做用 DSU 维护即可。
然后最后 30min 没写出来这个……gg
成功贡献一车罚时
Maximum Segment Sum
场上看一个人都没过就没看，其实不算难
考虑从左到右扫一遍，维护当前后缀和的最大值 cur，则我们要么做 cur←cur+1，要么 cur←max(cur−1,0)，然后这个过程中 cur 的最大值即为最大子段和。
然后你发现这个形如格路计数，熟悉反射容斥的小朋友们大概很容易就做出来了。
This Time I Will Be Lucky
也没有看……
等等我是不是在哪里见过？
哦哦应该不是
形如
f(a,b)=max(0,a+ba(f(a−1,b)+1)+a+bb(f(a,b−1)−1))
注意到答案没让我们取模，而且精度仅要求 10−6。
注意到如果每次不是减一而是减 ε→0+ 的话，我们实际上只会取到 y=abx 的 (x,y)。
所以这启示我们只要取接近 y=abx 的直线的附近的点进行计算即可。
Far Away
qtr 花了很久没想出来。
当时就隐隐约约觉得是不是在哪里见过了，场后降智解除之后忽然就发现确实做过的。
其实这道题是概率正确的。
如果在点数 ≤2×104 的连通块内，就直接输出 NO。
否则随机撒 300 个左右的点，跑 BFS，对每个询问 check 一次最短路，那么答案不正确当且仅当 (x,y) 的最短路完美避开了这 300 个点，概率是很低的。
Absolutely Flat
没看
考虑求出每个给定区间的已知元素中的 min 和 max，能否要求区间内的未知元素都在这个区间之内？
不难发现出现冲突当且仅当两个区间有交，且交集全部未确定。
还是很难做。考虑如果只有 0 和 1 能不能做。
那么我们就是要最小化同时有 0 和 1 的区间的数目。
承续上面的结构，我们发现难做的点形如 000???111???000???111...，其中每个区间只包括 0 和 ? 或者 1 和 ?。
每段颜色合并一下，其实难用 DP 解决。
Two Permutations
根本瞪不出来。
记 pi,j 表示 p1∼i 中 ≤j 的元素的数量。
那么结论是：合法当且仅当 pi,j≥qi,j,∀i,j。
虽然赛时想过逆序对方面的东西，但是没想到是这样刻画的。
证明太神秘了，赛时通过的人注意力惊人
首先必要性是显然的，因为操作只会让顺序对数量减少。
对于充分性，我们给出一个构造算法。
取最小的 x 使 p−1(x)=q−1(x)，显然此时必然 p−1(x)<q−1(x)。
令 k 为满足 p−1(x)<k≤q−1(x) 且 pk>x 的最小下标，这样的 k 必然存在。
我们断言：对于所有 p−1(x)≤l<k 且所有 x≤y<pk 必然有 pl,y>ql,y。
因此可以把 x 与 pk 交换。
重复此操作即可使 p=q。
One Permutation
可以猜想答案是凹的。
所以可以 WQS 二分。常规的 WQS 二分只能求出来一个值，怎么办呢？注意到只有 n 个 k 是有用的。这是因为答案的规模是 O(n) 的，显然斜率段数不可能很多。
注意这并不意味 k=O(n)，因为可能很陡。
每次怎么求出一个有用的 k？考虑维护一个 k 的区间，如果 L 和 R 得到的解是相同的，那么不用继续递归下去了。否则二分一下。
于是形如线段树修改，不增加时间复杂度的规模。
每次用一个树状数组维护 DP 即可。然后就做完了。时间复杂度 O(nnlogn)
Game on Board
qtr 场切了 %%%
注意到由于 x 和 y 不消失，所以实际上 max,max−gcd,max−2×gcd,…,max−k×gcd 都会出现。
所以判断一下游戏进行多少轮即可。